; vim: ts=4:et:sw=4:
; Copyleft (K) by Jose M. Rodriguez de la Rosa - (a.k.a. Boriel) - http://www.boriel.com
; This ASM library is licensed under the BSD license
; you can use it for any purpose (even for commercial closed source programs).
; Please read the BSD license on the internet

#include once <heapinit.asm>
; ---------------------------------------------------------------------
; MEM_FREE
;  Frees a block of memory
; Parameters:
;  HL = Pointer to the block to be freed. If HL is NULL (0) nothing
;  is done
; ---------------------------------------------------------------------
MEM_FREE:
__MEM_FREE:
; Frees the block pointed by HL
; HL DE BC & AF modified
                     ;- PROC
                     ;- LOCAL __MEM_LOOP2
                     ;- LOCAL __MEM_LINK_PREV
                     ;- LOCAL __MEM_JOIN_TEST
                     ;- LOCAL __MEM_BLOCK_JOIN
lda z80_h            ;- ld a,h
sta z80_a
ora z80_l            ;- or l
                     ;- ret z       ; Return if NULL pointer
                     ;- dec hl
                     ;- dec hl
lda z80_h            ;- ld b,h
sta z80_b
lda z80_l            ;- ld c,l    ; BC = Block pointer
sta z80_c
                     ;- ld hl, ZXBASIC_MEM_HEAP  ; This label point to the heap start

__MEM_LOOP2:
inc z80_l            ;- inc hl
bne *+4
inc z80_h
inc z80_l            ;- inc hl     ; Next block ptr
bne *+4
inc z80_h
ldy #$00             ;- ld e,(hl)
lda (z80_hl),y
sta z80_e
inc z80_l            ;- inc hl
bne *+4
inc z80_h
ldy #$00             ;- ld d,(hl) ; Block next ptr
lda (z80_hl),y
sta z80_d
lda z80_e            ;- ex de,hl  ; DE = &(block->next); HL = block->next
ldx z80_l
stx z80_e
sta z80_l
lda z80_d
ldx z80_h
stx z80_d
sta z80_h
                     ;- ld a, h    ; HL == NULL?
ora z80_l            ;- or l
                     ;- jp z, __MEM_LINK_PREV; if so, link with previous
ora z80_a            ;- or a       ; Clear carry flag
                     ;- sbc hl, bc ; Carry if BC > HL => This block if before
                     ;- add hl, bc ; Restores HL, preserving Carry flag
                     ;- jp c, __MEM_LOOP2 ; This block is before. Keep searching PASS the block

;------ At this point current HL is PAST BC, so we must link (DE) with BC, and HL in BC->next

__MEM_LINK_PREV:
; Link (DE) with BC, and BC->next with HL
lda z80_e            ;- ex de,hl
ldx z80_l
stx z80_e
sta z80_l
lda z80_d
ldx z80_h
stx z80_d
sta z80_h
lda z80_l            ;- push hl
pha
lda z80_h
pha
                     ;- dec hl
lda z80_c            ;- ld (hl),c
ldy #$00
sta (z80_hl),y
inc z80_l            ;- inc hl
bne *+4
inc z80_h
lda z80_b            ;- ld (hl),b ; (DE) <- BC
ldy #$00
sta (z80_hl),y
lda z80_b            ;- ld h,b    ; HL <- BC (Free block ptr)
sta z80_h
lda z80_c            ;- ld l,c
sta z80_l
inc z80_l            ;- inc hl     ; Skip block length (2 bytes)
bne *+4
inc z80_h
inc z80_l            ;- inc hl
bne *+4
inc z80_h
lda z80_e            ;- ld (hl),e ; Block->next = DE
ldy #$00
sta (z80_hl),y
inc z80_l            ;- inc hl
bne *+4
inc z80_h
lda z80_d            ;- ld (hl),d
ldy #$00
sta (z80_hl),y
; --- LINKED ; HL = &(BC->next) + 2
jsr __MEM_JOIN_TEST  ;- call __MEM_JOIN_TEST
pla                  ;- pop hl
sta z80_h
pla
sta z80_l

__MEM_JOIN_TEST:
; Checks for fragmented contiguous blocks and joins them
; hl = Ptr to current block + 2
ldy #$00             ;- ld d,(hl)
lda (z80_hl),y
sta z80_d
                     ;- dec hl
ldy #$00             ;- ld e,(hl)
lda (z80_hl),y
sta z80_e
                     ;- dec hl
ldy #$00             ;- ld b,(hl) ; Loads block length into BC
lda (z80_hl),y
sta z80_b
                     ;- dec hl
ldy #$00             ;- ld c,(hl)
lda (z80_hl),y
sta z80_c
lda z80_l            ;- push hl    ; Saves it for later
pha
lda z80_h
pha
lda z80_l            ;- add hl, bc ; Adds its length. If HL == DE now, it must be joined
clc
adc z80_c
sta z80_l
lda z80_h
adc z80_b
sta z80_h
ora z80_a            ;- or a
                     ;- sbc hl, de ; If Z, then HL == DE => We must join
pla                  ;- pop hl
sta z80_h
pla
sta z80_l
beq *+3              ;- ret nz
rts

__MEM_BLOCK_JOIN:  ; Joins current block (pointed by HL) with next one (pointed by DE). HL->length already in BC
lda z80_l            ;- push hl    ; Saves it for later
pha
lda z80_h
pha
lda z80_e            ;- ex de,hl
ldx z80_l
stx z80_e
sta z80_l
lda z80_d
ldx z80_h
stx z80_d
sta z80_h
ldy #$00             ;- ld e,(hl) ; DE -> block->next->length
lda (z80_hl),y
sta z80_e
inc z80_l            ;- inc hl
bne *+4
inc z80_h
ldy #$00             ;- ld d,(hl)
lda (z80_hl),y
sta z80_d
inc z80_l            ;- inc hl
bne *+4
inc z80_h
lda z80_e            ;- ex de,hl  ; DE = &(block->next)
ldx z80_l
stx z80_e
sta z80_l
lda z80_d
ldx z80_h
stx z80_d
sta z80_h
lda z80_l            ;- add hl,bc ; HL = Total Length
clc
adc z80_c
sta z80_l
lda z80_h
adc z80_b
sta z80_h
lda z80_h            ;- ld b,h
sta z80_b
lda z80_l            ;- ld c,l    ; BC = Total Length
sta z80_c
lda z80_e            ;- ex de,hl
ldx z80_l
stx z80_e
sta z80_l
lda z80_d
ldx z80_h
stx z80_d
sta z80_h
ldy #$00              ;- ld e,(hl)
lda (z80_hl),y
sta z80_e
inc z80_l            ;- inc hl
bne *+4
inc z80_h
ldy #$00             ;- ld d,(hl) ; DE = block->next
lda (z80_hl),y
sta z80_d
pla                  ;- pop hl     ; Recovers Pointer to block
sta z80_h
pla
sta z80_l
lda z80_c            ;- ld (hl),c
ldy #$00
sta (z80_hl),y
inc z80_l            ;- inc hl
bne *+4
inc z80_h
lda z80_b            ;- ld (hl),b ; Length Saved
ldy #$00
sta (z80_hl),y
inc z80_l            ;- inc hl
bne *+4
inc z80_h
lda z80_e            ;- ld (hl),e
ldy #$00
sta (z80_hl),y
inc z80_l            ;- inc hl
bne *+4
inc z80_h
lda z80_d            ;- ld (hl),d ; Next saved
ldy #$00
sta (z80_hl),y
rts                  ;- ret
                     ;- ENDP

;-------------------------------------------------------------------------------
; ----- IMPLEMENTATION NOTES ------
; The heap is implemented as a linked list of free blocks.
; Each free block contains this info:
; +----------------+ <-- HEAP START
; | Size (2 bytes) |
; |        0       | <-- Size = 0 => DUMMY HEADER BLOCK
; +----------------+
; | Next (2 bytes) |---+
; +----------------+ <-+
; | Size (2 bytes) |
; +----------------+
; | Next (2 bytes) |---+
; +----------------+   |
; | <free bytes...>|   | <-- If Size > 4, then this contains (size - 4) bytes
; | (0 if Size = 4)|   |
; +----------------+ <-+
; | Size (2 bytes) |
; +----------------+
; | Next (2 bytes) |---+
; +----------------+   |
; | <free bytes...>|   |
; | (0 if Size = 4)|   |
; +----------------+   |
;   <Allocated>        | <-- This zone is in use (Already allocated)
; +----------------+ <-+
; | Size (2 bytes) |
; +----------------+
; | Next (2 bytes) |---+
; +----------------+   |
; | <free bytes...>|   |
; | (0 if Size = 4)|   |
; +----------------+ <-+
; | Next (2 bytes) |--> NULL => END OF LIST
; |    0 = NULL    |
; +----------------+
; | <free bytes...>|
; | (0 if Size = 4)|
; +----------------+
; When a block is FREED, the previous and next pointers are examined to see
; if we can defragment the heap. If the block to be breed is just next to the
; previous, or to the next (or both) they will be converted into a single
; block (so defragmented).
;--   MEMORY MANAGER
; This library must be initialized calling __MEM_INIT with
; HL = BLOCK Start & DE = Length.
; An init directive is useful for initialization routines.
; They will be added automatically if needed.

